package it.storm.solution;

/**
 * 1764. 通过连接另一个数组的子数组得到一个数组
 * https://leetcode-cn.com/problems/form-array-by-concatenating-subarrays-of-another-array/
 */
public class Solutions_1764 {
    public static void main(String[] args) {
//        int[][] groups = {{1, -1, -1}, {3, -2, 0}};
//        int[] nums = {1, -1, 0, 1, -1, -1, 3, -2, 0};  // output: true

        int[][] groups = {{10, -2}, {1, 2, 3, 4}};
        int[] nums = {1, 2, 3, 4, 10, -2};  // output: false

//        int[][] groups = {{1, 2, 3}, {3, 4}};
//        int[] nums = {7, 7, 1, 2, 3, 4, 7, 7};  // output: false

        boolean result = canChoose(groups, nums);
        System.out.println(result);
    }

    /**
     * 解法二：暴力法优化（0ms）
     * 遍历 groups，依次判断 groups 中的数组是否在 nums 中存在
     * 定义变量 start 用于 nums 的起始循环位置，
     * 即固定了某一个 group 必须从 nums 数组的 start 位置开始检索
     */
    public static boolean canChoose(int[][] groups, int[] nums) {
        int start = 0;
        for (int[] group : groups) {
            int temp = hasSubArray(group, nums, start);
            if (temp == -1) {
                // [start, nums.length) 中，不包括 group 数组
                return false;
            }
            // 子数组不能相交
            start = temp + 1;
        }
        return true;
    }

    public static int hasSubArray(int[] target, int[] nums, int start) {
        while (start < nums.length) {
            int endIdx = start + target.length - 1;
            if (endIdx >= nums.length) {
                // [start, nums.length - 1] 的区间中元素个数小于 target 的元素个数
                break;
            }
            int i = start;
            for (; i <= endIdx; i++) {
                // 依次比较 nums、target 第 1，第 2，第 3... 个元素是否相同
                if (nums[i] != target[i - start]) {
                    break;
                }
            }
            if (i == endIdx + 1) {
                // 能够把 target 遍历完
                return endIdx;
            }
            start ++;
        }
        return -1;
    }

    /**
     * 解法一：暴力法（2ms）
     * 解题思路：递归方式实现
     * 循环 nums，直到 nums[i] == groups[curGroup][0]
     * 若相等，则判断 nums 的后续元素能否将 groups[curGroup] 数组遍历完
     * 若可以遍历完，则递归解决子问题：curGroup + 1
     * 最终 curGroup == gropus.length（即 nums 中的元素可以遍历完 groups），则 return true
     */
    public static boolean canChoose2(int[][] groups, int[] nums) {
        return dfs(nums, groups, 0, 0);
    }

    public static boolean dfs(int[] nums, int[][] groups, int start, int curGroup) {
        if (curGroup == groups.length) {
            // 结束条件：能够将 groups 遍历完
            return true;
        }
        for (int i = start; i < nums.length; i++) {
            if (nums[i] == groups[curGroup][0]) {
                // 第一个元素相等，则判断后续的元素
                int[] group = groups[curGroup];
                // 检查 nums[i + 1]，是否与 group[i] 相同
                int j = i + 1, k = 1;
                while (j < nums.length && k < group.length && nums[j] == group[k]) {
                    j ++;
                    k ++;
                }

                if (k == group.length) {
                    // 子问题：
                    // nums = nums[j, nums.length)
                    // curGroup + 1
                    boolean flag = dfs(nums, groups, j, curGroup + 1);
                    if (flag) {
                        // 递归返回 true
                        return true;
                    }
                }
            }
        }
        return false;
    }
}
